{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest String With Swaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestStringWithSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交换字符串中的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>，以及该字符串中的一些「索引对」数组&nbsp;<code>pairs</code>，其中&nbsp;<code>pairs[i] =&nbsp;[a, b]</code>&nbsp;表示字符串中的两个索引（编号从 0 开始）。</p>\n",
    "\n",
    "<p>你可以 <strong>任意多次交换</strong> 在&nbsp;<code>pairs</code>&nbsp;中任意一对索引处的字符。</p>\n",
    "\n",
    "<p>返回在经过若干次交换后，<code>s</code>&nbsp;可以变成的按字典序最小的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;dcab&quot;, pairs = [[0,3],[1,2]]\n",
    "<strong>输出：</strong>&quot;bacd&quot;\n",
    "<strong>解释：</strong> \n",
    "交换 s[0] 和 s[3], s = &quot;bcad&quot;\n",
    "交换 s[1] 和 s[2], s = &quot;bacd&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;dcab&quot;, pairs = [[0,3],[1,2],[0,2]]\n",
    "<strong>输出：</strong>&quot;abcd&quot;\n",
    "<strong>解释：</strong>\n",
    "交换 s[0] 和 s[3], s = &quot;bcad&quot;\n",
    "交换 s[0] 和 s[2], s = &quot;acbd&quot;\n",
    "交换 s[1] 和 s[2], s = &quot;abcd&quot;</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;cba&quot;, pairs = [[0,1],[1,2]]\n",
    "<strong>输出：</strong>&quot;abc&quot;\n",
    "<strong>解释：</strong>\n",
    "交换 s[0] 和 s[1], s = &quot;bca&quot;\n",
    "交换 s[1] 和 s[2], s = &quot;bac&quot;\n",
    "交换 s[0] 和 s[1], s = &quot;abc&quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= pairs.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= pairs[i][0], pairs[i][1] &lt;&nbsp;s.length</code></li>\n",
    "\t<li><code>s</code>&nbsp;中只含有小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-string-with-swaps](https://leetcode.cn/problems/smallest-string-with-swaps/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-string-with-swaps](https://leetcode.cn/problems/smallest-string-with-swaps/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"dcab\"\\n[[0,3],[1,2]]', '\"dcab\"\\n[[0,3],[1,2],[0,2]]', '\"cba\"\\n[[0,1],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size) -> None:\n",
    "        self.root = [i for i in range(size)]\n",
    "        self.rank = [1] * size\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x == self.root[x]:\n",
    "            return x\n",
    "        self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] < self.rank[rootY]:\n",
    "                self.root[rootX] = rootY\n",
    "            elif self.rank[rootX] > self.rank[rootY]:\n",
    "                self.root[rootY] = rootX\n",
    "            else:\n",
    "                self.root[rootX] = rootY\n",
    "                self.rank[rootY] += 1\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        uf = UnionFind(n)\n",
    "        for i, j in pairs:\n",
    "            uf.union(i, j)\n",
    "        group = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            group[uf.find(i)].append(i)\n",
    "        ans = [0] * n\n",
    "        for idxs in group.values():\n",
    "            sub = []\n",
    "            for idx in idxs:\n",
    "                sub.append(s[idx])\n",
    "            sub.sort()\n",
    "            i = 0\n",
    "            for idx in idxs:\n",
    "                ans[idx] = sub[i]\n",
    "                i += 1\n",
    "        return \"\".join(ans)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        parents, chs = dict(), dict()\n",
    "\n",
    "        def find(node):\n",
    "            if parents[node] == node:\n",
    "                return node\n",
    "\n",
    "            parent = find(parents[node])\n",
    "            parents[node] = parents[parents[node]]\n",
    "\n",
    "            return parent\n",
    "\n",
    "        def union(nodex, nodey):\n",
    "            rootx, rooty = find(nodex), find(nodey)\n",
    "            parents[rooty] = rootx\n",
    "\n",
    "        def getchs():\n",
    "            for node in parents:\n",
    "                root = find(node)\n",
    "                if root in chs:\n",
    "                    chs[root].append(s[node])\n",
    "                else:\n",
    "                    chs[root] = [s[node]]\n",
    "\n",
    "            for root in chs:\n",
    "                heapq.heapify(chs[root])\n",
    "\n",
    "        for pair in pairs:\n",
    "            p1, p2 = pair\n",
    "\n",
    "            if p1 not in parents:\n",
    "                parents[p1] = p1\n",
    "\n",
    "            if p2 not in parents:\n",
    "                parents[p2] = p2\n",
    "\n",
    "            union(p1, p2)\n",
    "\n",
    "        getchs()\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        for idx, ch in enumerate(s):\n",
    "            if idx not in parents:\n",
    "                ans.append(ch)\n",
    "            else:\n",
    "                ans.append(heapq.heappop(chs[find(idx)]))\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n:int):\n",
    "        self.root = list(range(n))\n",
    "        self.setCount = n \n",
    "    \n",
    "    def findroot(self, x:int)->int:\n",
    "        while self.root[x]!=x:\n",
    "            self.root[x] = self.root[self.root[x]]\n",
    "            x = self.root[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self,x:int, y:int)->bool:\n",
    "        root1,root2 = self.findroot(x),self.findroot(y)\n",
    "        if root1 == root2:\n",
    "            return False\n",
    "        self.root[root2] = root1\n",
    "        self.setCount-=1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        uf = UnionFind(n)\n",
    "        for i,j in pairs:\n",
    "            uf.union(i,j)\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            heapq.heappush(dic[uf.findroot(i)],s[i])\n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            char = heapq.heappop(dic[uf.findroot(i)])\n",
    "            ans+=char\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        parents = list(range(n))\n",
    "        partitions = defaultdict(list)\n",
    "\n",
    "        def find(x):\n",
    "            while x != parents[x]:\n",
    "                parents[x] = parents[parents[x]]\n",
    "                x = parents[x]\n",
    "            return x\n",
    "        \n",
    "        def union(x, y):\n",
    "            parents[find(x)] = find(y)\n",
    "        \n",
    "        for u, v in pairs:\n",
    "            union(u, v)\n",
    "        \n",
    "        for i, c in enumerate(s):\n",
    "            partitions[find(i)].append(c)\n",
    "        \n",
    "        for lst in partitions.values():\n",
    "            lst.sort(reverse=1)\n",
    "        \n",
    "        return ''.join(partitions[find(i)].pop() for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind():\n",
    "    def __init__(self,n):\n",
    "        self.parents = [ i for i in range(n)]\n",
    "\n",
    "    def union(self,x,y):\n",
    "        px = self.find(x)\n",
    "        py = self.find(y)\n",
    "        if px > py:\n",
    "            px,py = py,px\n",
    "\n",
    "        self.parents[py] = px\n",
    "\n",
    "    def find(self,x):\n",
    "        while self.parents[x] != x:\n",
    "            x = self.parents[x]\n",
    "        return x\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        uf = UnionFind(n)\n",
    "        for a,b in pairs:\n",
    "            uf.union(a, b)\n",
    "\n",
    "        areas = {}\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            pi = uf.find(i)\n",
    "            if not pi in areas:\n",
    "                areas[pi] = []\n",
    "            areas[pi].append(c)\n",
    "        for key in areas:\n",
    "            area = areas[key]\n",
    "            area.sort(reverse=True)\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            pi = uf.find(i)\n",
    "            char = areas[pi].pop()\n",
    "            ans += char\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        def find(x: int):\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x: int, y: int):\n",
    "            rx = find(x)\n",
    "            ry = find(y)\n",
    "            f[rx] = ry\n",
    "\n",
    "        n = len(s)\n",
    "        f = [i for i in range(n)]  # {son index: father index}\n",
    "        for i, j in pairs:\n",
    "            union(i, j)\n",
    "        # print(f)\n",
    "\n",
    "        \"\"\"\n",
    "        找出每一块连通分量的所有字符，排序后再放回原来的字符串，就是最后的答案\n",
    "        \"\"\"\n",
    "        mp = defaultdict(list)  # {root index: [son char...]}\n",
    "        # 遍历f, 将连通分量内的所有字符加入pool字典\n",
    "        for i in range(n):\n",
    "            heapq.heappush(mp[find(i)], s[i])\n",
    "        # print(mp)\n",
    "\n",
    "        res = \"\"\n",
    "        for i in range(n):\n",
    "            x = heapq.heappop(mp[find(i)])\n",
    "            res += x\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        #pairs.sort()\n",
    "        # 找到连通的子序列，这个子序列可以降为最小\n",
    "        n = len(s)\n",
    "        st = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if st[x] != x: \n",
    "                st[x] = find(st[x])\n",
    "            return st[x]\n",
    "        for x, y in pairs:\n",
    "            r_x, r_y = find(x), find(y)\n",
    "            if r_x != r_y:\n",
    "                st[r_x] = r_y \n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            r = find(i)\n",
    "            if mp.get(r, -1) == -1:\n",
    "                mp[r] = [i]\n",
    "            else:\n",
    "                mp[r].append(i)\n",
    "        ans = list(s)\n",
    "        for idx in mp.values(): # 同属于一个根的下标\n",
    "            idx.sort()\n",
    "            sub = sorted(ans[i] for i in idx) # 把形成了连通块的字符排序\n",
    "            for i, c in zip(idx, sub): # 把排好序的字符放到原来连通块占有的idx中\n",
    "                ans[i] = c \n",
    "        return \"\".join(ans)\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.fa = [i for i in range(n)]\n",
    "    def find(self, x):\n",
    "        while x != self.fa[x]:\n",
    "            self.fa[x] = self.fa[self.fa[x]]\n",
    "            x = self.fa[x]\n",
    "        return x\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        self.fa[root_x] = root_y\n",
    "        return True\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        size = len(s)\n",
    "        uf = UnionFind(size)\n",
    "        for i, j in pairs:\n",
    "            uf.union(i, j)\n",
    "        s_dict = defaultdict(list)\n",
    "        for i in range(size):\n",
    "            root_i = uf.find(i)\n",
    "            s_dict[root_i].append(i)\n",
    "        res = list(s)\n",
    "        for indices in s_dict.values():\n",
    "            string = sorted(res[indice] for indice in indices)\n",
    "            for i, ch in zip(indices, string):\n",
    "                res[i] = ch\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 很显然是连通域原理，用并查集解决问题\n",
    "        n = len(s)\n",
    "        p = [i for i in range(n)]\n",
    "\n",
    "        def find(node):\n",
    "            while p[node] != node:\n",
    "                p[node] = p[p[node]]\n",
    "                node = p[node]\n",
    "            return node\n",
    "\n",
    "        def union(a, b):\n",
    "            root_a, root_b = find(a), find(b)\n",
    "            if root_a != root_b:\n",
    "                p[root_a] = root_b\n",
    "        \n",
    "        for u, v in pairs:\n",
    "            union(u, v)\n",
    "        \n",
    "        m = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            m[find(i)].append(i)\n",
    "        \n",
    "        s = list(s)\n",
    "        for k in m:\n",
    "            nums = sorted(m[k])\n",
    "            s1 = sorted([s[i] for i in nums])\n",
    "            for i, c in zip(nums, s1):\n",
    "                s[i] = c\n",
    "        \n",
    "        return ''.join(s)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n=len(s)\n",
    "        fa=list(range(n))\n",
    "        def find(a):\n",
    "            if fa[a]!=a:\n",
    "                fa[a]=find(fa[a])\n",
    "            return fa[a]\n",
    "        for x,y in pairs:\n",
    "            fa[find(x)]=find(y)\n",
    "        idx=defaultdict(list)\n",
    "        ch=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            idx[find(i)].append(i)\n",
    "            ch[find(i)].append(s[i])\n",
    "        res=[None]*n\n",
    "        for x in list(idx.keys()):\n",
    "            idx[x].sort()\n",
    "            ch[x].sort()\n",
    "            for i,c in zip(idx[x],ch[x]):\n",
    "                res[i]=c\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        parent = {}\n",
    "        def find(x):\n",
    "            parent.setdefault(x, x)\n",
    "            if parent[x] == x:\n",
    "                return x\n",
    "            parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x, y):\n",
    "            parent[find(x)] = find(y)\n",
    "        def connected(x, y):\n",
    "            return find(x) == find(y)\n",
    "        for x, y in pairs:\n",
    "            union(x, y)\n",
    "        ret = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            ret[find(i)].append(c)\n",
    "        for r in ret.values():\n",
    "            r.sort()\n",
    "        cnt = [0] * n \n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            ans += ret[parent[i]][cnt[parent[i]]]\n",
    "            cnt[parent[i]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self,res,graph,visited,x):\n",
    "        queue = collections.deque([x])\n",
    "        visited[x] = 1\n",
    "        res.append(x)\n",
    "        \n",
    "        while queue:\n",
    "            cur_node = queue.popleft()\n",
    "            for neighbor in graph[cur_node]:\n",
    "                if visited[neighbor]:\n",
    "                    continue\n",
    "                visited[neighbor] = 1\n",
    "                res.append(neighbor)\n",
    "                queue.append(neighbor)\n",
    "    \n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(len(s))]\n",
    "        visited = [0] * len(s)\n",
    "        for x,y in pairs:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        res = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if not visited[i]:\n",
    "                # 获取联通节点\n",
    "                connected_nodes = []\n",
    "                self.bfs(connected_nodes,graph,visited,i)\n",
    "                # 重新赋值\n",
    "                indices = sorted(connected_nodes)\n",
    "                string = sorted(res[node] for node in connected_nodes)\n",
    "                for j,ch in zip(indices,string):\n",
    "                    res[j] = ch\n",
    "            \n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1. 只要连通分量，随便换位置\n",
    "# 2. 问题就是找几个连通分量，用 Dsu\n",
    "# 3. 遍历字符串，放进各自分量，各个分量排序\n",
    "# 4. 遍历，找到位置对应分量，弹出一个字符\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}  # {child: father} 创建一个字典，用来存储每个节点的父节点\n",
    "\n",
    "    def find(self, x):\n",
    "        self.father.setdefault(x, x)  # 如果 x 在 father 字典中不存在，则添加 x,且他的父亲就是自己\n",
    "        if self.father[x] != x:  # 如果 x 不是根节点\n",
    "            self.father[x] = self.find(self.father[x])  # 递归地找到child的根节点，并将其赋值给child的父节点，实现路径压缩\n",
    "        return self.father[x]  # 返回child的根节点\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.father[self.find(y)] = self.find(x)  # 将x所属的集合的根节点的父节点设为y所属的集合的根节点，实现两个集合的合并\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 并查集建图\n",
    "        uf = UnionFind()\n",
    "        for x, y in pairs:\n",
    "            uf.union(x, y)  # 将字母对放入并查集中\n",
    "\n",
    "        # 获取联通节点\n",
    "        connected_components = collections.defaultdict(list)\n",
    "        for node in range(len(s)):\n",
    "            connected_components[uf.find(node)].append(node)  # 将联通的字母索引放入同一列表\n",
    "\n",
    "        res = list(s)\n",
    "        # 重新赋值\n",
    "        for nodes in connected_components.values():\n",
    "            indices = nodes\n",
    "            string = sorted(res[node] for node in nodes)  # 对每个列表排序\n",
    "            for i, ch in zip(indices, string):\n",
    "                res[i] = ch  # 按排序结果重新赋值\n",
    "        return \"\".join(res)\n",
    "# 作者：Hao Kun Yang\n",
    "# 链接：https://leetcode.cn/problems/smallest-string-with-swaps/solutions/555169/python-bing-cha-ji-dfsbfssan-chong-jie-f-yy89/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "\n",
    "        if root != x:\n",
    "            old_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = old_father\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "        \n",
    "    def is_connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        if not pairs:\n",
    "            return s\n",
    "\n",
    "        uf = UnionFind()\n",
    "        for i in range(len(s)):\n",
    "            uf.add(i)\n",
    "        for first, second in pairs:\n",
    "            uf.merge(first, second)\n",
    "\n",
    "        groups = {}\n",
    "        for i in range(len(s)):\n",
    "            root = uf.find(i)\n",
    "            if root in groups:\n",
    "                groups[root].append(s[i])\n",
    "            else:\n",
    "                groups[root] = [s[i]]\n",
    "\n",
    "        for root, group in groups.items():\n",
    "            group.sort(reverse = True)\n",
    "\n",
    "        result = []\n",
    "        for i in range(len(s)):\n",
    "            root = uf.find(i)\n",
    "            result.append(groups[root].pop())\n",
    "\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        fa = list(range(n))\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        for a,b in pairs:\n",
    "            union(a,b)\n",
    "        \n",
    "        mp = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            mp[find(i)].append((c, i))\n",
    "        \n",
    "        ans = ['a'] * n\n",
    "        for vec in mp.values():\n",
    "            vec.sort(key=lambda p:p[0])\n",
    "            idx = sorted(p[1] for p in vec)\n",
    "            for i, (c, _) in zip(idx, vec):\n",
    "                ans[i] = c\n",
    "        \n",
    "        return \"\".join(ans)\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = list(range(n))\n",
    "\n",
    "    def find(self, num):\n",
    "        while num != self.parents[num]:\n",
    "            self.parents[num] = self.parents[self.parents[num]]\n",
    "            num = self.parents[num]\n",
    "        return num\n",
    "\n",
    "    def union(self, num1, num2):\n",
    "        parent1, parent2 = self.find(num1), self.find(num2)\n",
    "        if parent1 == parent2:\n",
    "            return\n",
    "        if num1 <= num2:\n",
    "            self.parents[parent2] = parent1\n",
    "        else:\n",
    "            self.parents[parent1] = parent2\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        uf = UnionFind(n)\n",
    "        for idx1, idx2 in pairs:\n",
    "            uf.union(idx1, idx2)\n",
    "\n",
    "        merged_blocks = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            merged_blocks[uf.find(i)].append([i, c])\n",
    "\n",
    "        ans = [\"\"] * n\n",
    "        for mb in merged_blocks.values():\n",
    "            mb.sort(key = lambda x : x[1])\n",
    "            indices = [i for i, c in mb]\n",
    "            indices.sort()\n",
    "            for i, (_, c) in zip(indices, mb):\n",
    "                ans[i] = c\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: [int]) -> str:\n",
    "        p = {i:i for i in range(len(s))}    #初始化并查集\n",
    "\n",
    "        def f(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = f(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        for i, j in pairs:\n",
    "            p[f(j)] = f(i)      \n",
    "        #合并可交换位置\n",
    "        d = collections.defaultdict(list)\n",
    "        for i, j in enumerate(map(f, p)):\n",
    "            d[j].append(i)\n",
    "        #排序\n",
    "        ans = list(s)\n",
    "        for q in d.values():\n",
    "            t = sorted(ans[i] for i in q)   \n",
    "            for i, c in zip(sorted(q), t):\n",
    "                ans[i] = c\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        记录每个节点的父节点\n",
    "        记录每个节点到根节点的权重\n",
    "        \"\"\"\n",
    "        self.father = {}\n",
    "        self.value = {}\n",
    "    \n",
    "    def find(self,x):\n",
    "        \"\"\"\n",
    "        查找根节点\n",
    "        路径压缩\n",
    "        更新权重\n",
    "        \"\"\"\n",
    "        root = x\n",
    "        # 节点更新权重的时候要放大的倍数\n",
    "        base = 1\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "            #base *= self.value[root]\n",
    "        \n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            if x == 0 and root == 2:\n",
    "                print(original_father)\n",
    "            ##### 离根节点越远，放大的倍数越高\n",
    "            #self.value[x] *= base\n",
    "            #base /= self.value[original_father]\n",
    "            #####\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "         \n",
    "        return root\n",
    "    \n",
    "    def merge(self,x,y,val):\n",
    "        \"\"\"\n",
    "        合并两个节点\n",
    "        \"\"\"\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            ##### 四边形法则更新根节点的权重\n",
    "            #self.value[root_x] = self.value[y] * val / self.value[x]\n",
    "\n",
    "    def is_connected(self,x,y):\n",
    "        \"\"\"\n",
    "        两节点是否相连\n",
    "        \"\"\"\n",
    "        return x in self.value and y in self.value and self.find(x) == self.find(y)\n",
    "    \n",
    "    def add(self,x):\n",
    "        \"\"\"\n",
    "        添加新节点，初始化权重为1.0\n",
    "        \"\"\"\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            #self.value[x] = 1.0\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 并查集建图\n",
    "        uf = UnionFind()\n",
    "        for i in range(len(s)):\n",
    "            uf.add(i)\n",
    "            \n",
    "        for x,y in pairs:\n",
    "            uf.merge(x,y, 0)\n",
    "            \n",
    "        # 获取联通节点\n",
    "        connected_components = collections.defaultdict(list)\n",
    "        for node in range(len(s)):\n",
    "            connected_components[uf.find(node)].append(node)\n",
    "        \n",
    "        res = [''] *len(s)\n",
    "        print(res)\n",
    "        print(connected_components)\n",
    "        # 重新赋值\n",
    "        for nodes in connected_components.values():\n",
    "            indices = nodes\n",
    "            string = sorted(s[node] for node in nodes)\n",
    "            print('ccc', nodes, string)\n",
    "            for i,ch in zip(indices,string):\n",
    "                res[i] = ch\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for a, b in pairs:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        visit = set()\n",
    "        for entry in graph:\n",
    "            if entry in visit:\n",
    "                continue\n",
    "            que = deque([entry])\n",
    "            visit.add(entry)\n",
    "            aera = []\n",
    "            while que:\n",
    "                a = que.popleft()\n",
    "                aera.append(a)\n",
    "                for b in graph[a]:\n",
    "                    if b in visit:\n",
    "                        continue\n",
    "                    que.append(b)\n",
    "                    visit.add(b)\n",
    "            aera.sort()\n",
    "            sub_ls = sorted(s[i] for i in aera)\n",
    "            for j, c in zip(aera, sub_ls):\n",
    "                s[j] = c\n",
    "\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        class UnionFind():\n",
    "            def __init__(self, n):\n",
    "                self.parent = list(range(n))\n",
    "                self.values = [1] * n\n",
    "            def find(self, x):\n",
    "                if x != self.parent[x]:\n",
    "                    root = self.find(self.parent[x])\n",
    "                    self.parent[x] = root\n",
    "                return self.parent[x]\n",
    "            def union(self, x, y):\n",
    "                root_x = self.find(x)\n",
    "                root_y = self.find(y)\n",
    "                if root_x != root_y:\n",
    "                    if self.values[root_x] < self.values[root_y]:\n",
    "                        self.parent[root_x] = root_y\n",
    "                        self.values[root_y] += self.values[root_x]\n",
    "                    else:\n",
    "                        self.parent[root_y] = root_x\n",
    "                        self.values[root_x] += self.values[root_y]\n",
    "            def isConnected(self, x, y):\n",
    "                return self.find(x) == self.find(y)\n",
    "        \n",
    "        # 能相互交换的字母是联通的\n",
    "        uf = UnionFind(len(s))\n",
    "        for pair in pairs:\n",
    "            uf.union(pair[0], pair[1])\n",
    "\n",
    "        # 联通的字母放一起\n",
    "        merge_i = [[] for i in range(len(s))]\n",
    "        merge_s = [[] for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            root = uf.find(i)\n",
    "            merge_i[root].append(i)\n",
    "            merge_s[root].append(s[i])\n",
    "        \n",
    "        # 输出\n",
    "        res = [0] * len(s)\n",
    "        for mi, ms in zip(merge_i, merge_s):\n",
    "            if (len(ms)) == 0: continue\n",
    "            ms.sort()\n",
    "            for i in range(len(mi)):\n",
    "                res[mi[i]] = ms[i]\n",
    "        return \"\".join(res)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, pa, x):\n",
    "        if pa[x] != x:\n",
    "            pa[x] = self.find(pa, pa[x])\n",
    "        return pa[x]\n",
    "    \n",
    "    def union(self, x ,y, pa):\n",
    "        fx = self.find(pa, x)\n",
    "        fy = self.find(pa, y)\n",
    "        if fx != fy:\n",
    "            pa[fx] = fy\n",
    "    \n",
    "    def is_connect(self, x, y, pa):\n",
    "        return self.find(pa, x) == self.find(pa, y)\n",
    "    \n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        pa = [ i for i in range(n)]\n",
    "        for pair in pairs:\n",
    "            self.union(pair[0], pair[1], pa)\n",
    "        # 找到每个联通分量\n",
    "        componet_s = [ [] for i in range(n)]\n",
    "        componet_idx = [ [] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            pi = self.find(pa, i)\n",
    "            componet_s[pi].append(s[i])\n",
    "            componet_idx[pi].append(i)\n",
    "        # print(componet_s)\n",
    "        for com_i in componet_s:\n",
    "            com_i.sort()\n",
    "        \n",
    "        res= ['0'] * n\n",
    "        for i in range(len(componet_idx)):\n",
    "            for j in range(len(componet_idx[i])):\n",
    "                res[componet_idx[i][j]] = componet_s[i][j]\n",
    "\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    p = []\n",
    "\n",
    "    def find(self, x) -> int:\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        self.p = [i for i in range(n + 1)]\n",
    "        for i in range(len(pairs)):\n",
    "            a, b = pairs[i][0], pairs[i][1]\n",
    "            pa, pb = self.find(a), self.find(b)\n",
    "            if pa != pb:\n",
    "                self.p[pa] = pb\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            pa = self.find(i)\n",
    "            l.append(pa)\n",
    "            # print(pa)\n",
    "        q = zip(s, range(n))\n",
    "        q = zip(q, l)\n",
    "        sort_a = sorted(q, key=lambda x: x[1])\n",
    "        list_a = list(sort_a)\n",
    "        i = 0\n",
    "        res = [0 for i in range(n)]\n",
    "        while i < n:\n",
    "            st = i\n",
    "            i += 1\n",
    "            while i < n and list_a[i - 1][1] == list_a[i][1]:\n",
    "                i += 1\n",
    "            sub = list_a[st:i]\n",
    "            sort_sub1 = sorted(sub, key=lambda x: x[0][0])\n",
    "            sort_sub2 = sorted(sub, key=lambda x: x[0][1])\n",
    "            for j in range(len(sort_sub1)):\n",
    "                res[sort_sub2[j][0][1]] = sort_sub1[j][0][0]\n",
    "        \n",
    "        ans = ''.join(res)\n",
    "        return ans\n",
    "        # print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFather(self, father: List[int], x: int) -> int:\n",
    "        root = x\n",
    "        while father[root] != root:\n",
    "            root = father[root]\n",
    "\n",
    "        # 路径压缩\n",
    "        while x != root:\n",
    "            original_father = father[x]\n",
    "            father[x] = root\n",
    "            x = original_father\n",
    "\n",
    "        return root\n",
    "\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 要是字符串字典序最小，故下标小的字符需要字典序最小\n",
    "        # 构建并查集，是相同组内的数据按字典序排列\n",
    "        n = len(s)\n",
    "        # 定义father数组\n",
    "        father = [i for i in range(n)]\n",
    "        # 定义按组聚合的数据集\n",
    "        map = {}\n",
    "        for i in range(n):\n",
    "            map[i] = [s[i]]\n",
    "        for i, j in pairs:\n",
    "            x, y = self.findFather(father, i), self.findFather(father, j)\n",
    "            if x != y:\n",
    "                father[y] = x\n",
    "                # map也合并\n",
    "                map[x] += map.pop(y)\n",
    "        # 对map的val进行排序\n",
    "        for k in map.keys():\n",
    "            map[k].sort()\n",
    "        # 重新输出字符串\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            x = self.findFather(father, i)\n",
    "            res += map[x].pop(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        def union(x, y):\n",
    "            xx = find(x)\n",
    "            yy = find(y)\n",
    "            if xx != yy:\n",
    "                if rank[xx] > rank[yy]:\n",
    "                    xx, yy = yy, xx\n",
    "                parent[xx] = yy\n",
    "                if rank[yy] == rank[xx]:\n",
    "                    rank[yy] += 1\n",
    "        \n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        m = len(s)\n",
    "        parent = {i: i for i in range(m)}\n",
    "        rank = {i: 1 for i in range(m)}\n",
    "        \n",
    "        for a, b in pairs:\n",
    "            union(a, b)\n",
    "        \n",
    "        tmp = list(s)\n",
    "        pa = set()\n",
    "        areas = collections.defaultdict(list)\n",
    "        \n",
    "        for i in range(m):\n",
    "            t = find(i)\n",
    "            pa.add(t)\n",
    "            areas[t].append(i)\n",
    "        \n",
    "        for j in pa:\n",
    "            tt = [0] * len(areas[j])\n",
    "            for i in range(len(areas[j])):\n",
    "                tt[i] = s[areas[j][i]]\n",
    "            tt.sort()\n",
    "            areas[j].sort()\n",
    "            for index, value in zip(areas[j], tt):\n",
    "                tmp[index] = value\n",
    "        return \"\".join(tmp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n, s):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.toKey = {i: [s[i]] for i in range(n)}\n",
    "        self.s = s\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x == self.root[x]:\n",
    "            return x\n",
    "        self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "    \n",
    "\n",
    "    def union(self, u, v):\n",
    "        pu, pv = self.find(u), self.find(v)\n",
    "        if pu == pv:\n",
    "            return False\n",
    "        if pu > pv:\n",
    "            pu, pv = pv, pu\n",
    "        self.root[pv] = pu\n",
    "        self.toKey[pu] = self.toKey[pu] + self.toKey[pv]\n",
    "        return True\n",
    "    \n",
    "    def sort(self):\n",
    "        for k in self.toKey:\n",
    "            self.toKey[k].sort()\n",
    "    \n",
    "    def getCharFor(self, x):\n",
    "        px = self.find(x)\n",
    "        r = self.toKey[px][0]\n",
    "        self.toKey[px].pop(0)\n",
    "        return r\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        uf = UnionFind(len(s), s)\n",
    "        for a, b in pairs:\n",
    "            uf.union(a, b)\n",
    "        uf.sort()\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            res.append(uf.getCharFor(i))\n",
    "        return ''.join(res)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union:\n",
    "    def __init__(self, n):\n",
    "        self.fa = [i for i in range(n + 1)]\n",
    "        self.cnt = [1 for i in range(n + 1)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.fa[x] == x:\n",
    "            return x\n",
    "        root = self.find(self.fa[x])\n",
    "        self.fa[x] = root\n",
    "        return root\n",
    "        # return self.fa[x] if self.fa[x] == x else self.find(self.fa[x])\n",
    "    def merge(self, a, b):\n",
    "        ra = self.find(a)\n",
    "        rb = self.find(b)\n",
    "        if  ra == rb:\n",
    "            return\n",
    "        self.cnt[rb] += self.cnt[ra]\n",
    "        self.fa[ra] = rb\n",
    "        return\n",
    "\n",
    "\n",
    "class Heap:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "    def push(self, val):\n",
    "        self.data.append(val)\n",
    "        ind = self.size() - 1\n",
    "        f_ind = (ind - 1) // 2\n",
    "        while f_ind >= 0 and self.data[ind] < self.data[f_ind]:\n",
    "            self.data[f_ind], self.data[ind] = self.data[ind], self.data[f_ind]\n",
    "            ind = f_ind\n",
    "            f_ind = (ind - 1) // 2\n",
    "        return\n",
    "    def pop(self):\n",
    "        if self.size() == 0:\n",
    "            return\n",
    "        out = self.data[0]\n",
    "        self.data[0] = self.data[-1]\n",
    "        self.data.pop()\n",
    "        ind = 0\n",
    "        n = self.size() - 1\n",
    "        while 2 * ind + 1 <= n:\n",
    "            temp = ind\n",
    "            if self.data[temp] > self.data[ind * 2 + 1]:\n",
    "                temp = ind * 2 + 1\n",
    "            if ind * 2 + 2 <= n and self.data[temp] > self.data[ind * 2 + 2]:\n",
    "                temp = ind * 2 + 2\n",
    "            if temp == ind:\n",
    "                break\n",
    "            self.data[temp], self.data[ind] = self.data[ind], self.data[temp]\n",
    "            ind = temp\n",
    "        return out\n",
    "    def top(self):\n",
    "        if self.data:\n",
    "            return self.data[0]\n",
    "        else:\n",
    "            return None\n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        u = Union(n)\n",
    "        h = [Heap() for i in range(n)]\n",
    "\n",
    "        for item in pairs:\n",
    "            u.merge(item[0], item[1])\n",
    "        \n",
    "        for i in range(n):\n",
    "            h[u.find(i)].push(ord(s[i]))\n",
    "        \n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            res += chr(h[u.find(i)].pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        # 邻接表\n",
    "        adj = [set() for _ in range(n)]\n",
    "        for i, j in pairs:\n",
    "            if i != j:\n",
    "                adj[i].add(j)\n",
    "                adj[j].add(i)\n",
    "\n",
    "        visited = [False] * n\n",
    "        result = [\"\"] * n\n",
    "        for idx in range(n):\n",
    "            if not visited[idx]:\n",
    "                component = []\n",
    "                # bfs\n",
    "                queue = Queue()\n",
    "                ptr = idx\n",
    "                while 1:\n",
    "                    if not visited[ptr]:\n",
    "                        visited[ptr] = True\n",
    "                        component.append(ptr)\n",
    "                        for nbr in adj[ptr]:\n",
    "                            if not visited[nbr]:\n",
    "                                queue.put(nbr)\n",
    "                    if queue.empty():\n",
    "                        break\n",
    "                    ptr = queue.get()\n",
    "\n",
    "                component.sort()\n",
    "                tmp = [s[i] for i in component]\n",
    "                tmp.sort()\n",
    "                for i, char in zip(component, tmp):\n",
    "                    result[i] = char\n",
    "        \n",
    "        return \"\".join(result)\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MergeSearch():\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.father = self\n",
    "\n",
    "    def setFather(self, Node):\n",
    "        self.findFather()\n",
    "        self.father.father = Node.findFather()\n",
    "\n",
    "    def findFather(self):\n",
    "        if self.father != self.father.father:\n",
    "            self.father = self.father.findFather()\n",
    "        return self.father\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        Nodes = [MergeSearch(i) for i in range(n)]\n",
    "        ans = [\"a\"] * n\n",
    "        for u, v in pairs:\n",
    "            Nodes[u].setFather(Nodes[v])\n",
    "        idxes = defaultdict(list)\n",
    "        words = defaultdict(list)\n",
    "        for i, node in enumerate(Nodes):\n",
    "            idxes[node.findFather().val].append(i)\n",
    "            words[node.findFather().val].append(s[i])\n",
    "        for idx in idxes:\n",
    "            indexes = idxes[idx]\n",
    "            word = words[idx]\n",
    "            word.sort()\n",
    "            for index, w in zip(indexes, word):\n",
    "                ans[index] = w\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        groups = {i : [i] for i in range(len(s))}\n",
    "        parent = {i : i for i in range(len(s))}\n",
    "        for p,q in pairs:\n",
    "            if parent[p] != parent[q]:\n",
    "                qq = parent[q]\n",
    "                pp = parent[p]\n",
    "                if len(groups[pp]) > len(groups[qq]):\n",
    "                    for i in groups[qq]:\n",
    "                        parent[i] = pp\n",
    "                    groups[pp].extend(groups.pop(qq))\n",
    "                else:\n",
    "                    for i in groups[pp]:\n",
    "                        parent[i] = qq\n",
    "                    groups[qq].extend(groups.pop(pp))\n",
    "        res = \"\"\n",
    "        for i in groups:\n",
    "            groups[i].sort(key = lambda x:s[x])\n",
    "        for i in range(len(s)):\n",
    "            res += s[groups[parent[i]].pop(0)]\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        graph = {i :[] for i in range(n)}\n",
    "\n",
    "        for u, v in pairs:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        visited = set()\n",
    "        char_list = [None for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            # 找出连通分量\n",
    "            component = self.bfs(graph, i)\n",
    "            # ！！！注意集合的并集操作\n",
    "            visited |= component\n",
    "            # 将分量中的索引和字母都进行排序\n",
    "            char = sorted([s[i] for i in component])\n",
    "            idx = sorted(list(component))\n",
    "            # 依次放入字符\n",
    "            for c, idx in zip(char, idx):\n",
    "                char_list[idx] = c\n",
    "        \n",
    "        return \"\".join(char_list)\n",
    "    \n",
    "\n",
    "    def bfs(self, graph, i):\n",
    "        queue = deque([i])\n",
    "        visited = set([i])\n",
    "\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "\n",
    "            for v in graph[u]:\n",
    "                if v in visited:\n",
    "                    continue\n",
    "                \n",
    "                queue.append(v)\n",
    "                visited.add(v)\n",
    "        \n",
    "        return visited\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s, pairs):\n",
    "        uf = dict()\n",
    "        dic = defaultdict(SortedList)\n",
    "        indexDict = defaultdict(int)\n",
    "        numDict = dict()\n",
    "        def find(x):\n",
    "            if uf[x] != x:\n",
    "                uf[x] = find(uf[x])\n",
    "            return uf[x]\n",
    "        sLen = len(s)\n",
    "        for i in range(sLen):\n",
    "            uf[i] = i\n",
    "        for a,b in pairs:\n",
    "            uf[find(a)] = find(b)\n",
    "        for i in range(sLen):\n",
    "            root = find(i)\n",
    "            dic[root].add(s[i])\n",
    "            numDict[i] = indexDict[root]\n",
    "            indexDict[root] += 1\n",
    "        result = ''\n",
    "        for i in range(sLen):\n",
    "            result += dic[find(i)][numDict[i]]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        edges = collections.defaultdict(set)\n",
    "        for i,j in pairs:\n",
    "            edges[i].add(j)\n",
    "            edges[j].add(i)\n",
    "\n",
    "        visited = [False] * n\n",
    "        s = list(s)\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i] = True\n",
    "                queue = [i]\n",
    "                for j in queue:\n",
    "                    for k in edges[j]:\n",
    "                        if not visited[k]:\n",
    "                            visited[k] = True \n",
    "                            queue.append(k)\n",
    "\n",
    "                chars = sorted([s[j]for j in queue])\n",
    "                idxs = sorted(queue)\n",
    "                for j, c in zip(idxs, chars):\n",
    "                    s[j] = c\n",
    "                       \n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        # 邻接表\n",
    "        adj = [set() for _ in range(n)]\n",
    "        for i, j in pairs:\n",
    "            if i != j:\n",
    "                adj[i].add(j)\n",
    "                adj[j].add(i)\n",
    "\n",
    "        visited = set()\n",
    "        components = []\n",
    "        for idx in range(n):\n",
    "            if idx not in visited:\n",
    "                components.append([])\n",
    "                # bfs\n",
    "                queue = Queue()\n",
    "                ptr = idx\n",
    "                while 1:\n",
    "                    if ptr not in visited:\n",
    "                        visited.add(ptr)\n",
    "                        components[-1].append(ptr)\n",
    "                        for nbr in adj[ptr]:\n",
    "                            if nbr not in visited:\n",
    "                                queue.put(nbr)\n",
    "                    if queue.empty():\n",
    "                        break\n",
    "                    ptr = queue.get()\n",
    "        \n",
    "        result = [\"\"] * n\n",
    "        for comp in components:\n",
    "            comp.sort()\n",
    "            tmp = [s[i] for i in comp]\n",
    "            tmp.sort()\n",
    "            for i, char in zip(comp, tmp):\n",
    "                result[i] = char\n",
    "        return \"\".join(result)\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        maps={}\n",
    "        for idx in pairs:\n",
    "            if idx[0] not in maps:\n",
    "                maps[idx[0]]=set()\n",
    "            if idx[1] not in maps:\n",
    "                maps[idx[1]]=set()\n",
    "            maps[idx[0]].add(idx[1])\n",
    "            maps[idx[1]].add(idx[0])\n",
    "        active=[0 for i in range(len(s))]\n",
    "        vec=[s[i] for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if active[i]==1:\n",
    "                continue\n",
    "            allpoint=set()\n",
    "            curpoint=set([i])\n",
    "            while len(curpoint)>0:\n",
    "                nextpoints=set()\n",
    "                for point in curpoint:\n",
    "                    active[point]=1\n",
    "                    allpoint.add(point)\n",
    "                    if point in maps:\n",
    "                        for newpoint in maps[point]:\n",
    "                            if newpoint not in allpoint and newpoint not in curpoint:\n",
    "                                nextpoints.add(newpoint)\n",
    "                curpoint=nextpoints.copy()\n",
    "            idx=list(allpoint)\n",
    "            val=[]\n",
    "            for j in idx:\n",
    "                val.append(s[j])\n",
    "            val.sort()\n",
    "            idx.sort()\n",
    "            for j in range(len(idx)):\n",
    "                vec[idx[j]]=val[j]\n",
    "        return \"\".join(vec)\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        pairs_dict = defaultdict(set)\n",
    "        for i, j in pairs:\n",
    "            if i == j:\n",
    "                continue\n",
    "            pairs_dict[i].add(j)\n",
    "            pairs_dict[j].add(i)\n",
    "\n",
    "        def dfs(i):\n",
    "            connected_idxs.append(i)\n",
    "            connected_vals.append(s[i])\n",
    "            visited[i] = True\n",
    "            for j in pairs_dict[i]:\n",
    "                if not visited[j]:\n",
    "                    dfs(j)\n",
    "        def bfs(i):\n",
    "            queue = deque([i])\n",
    "            while queue:\n",
    "                idx = queue.popleft()\n",
    "                connected_vals.append(s[idx])\n",
    "                connected_idxs.append(idx)\n",
    "                visited[idx] = True\n",
    "                for next_idx in pairs_dict[idx]:\n",
    "                    if visited[next_idx] or next_idx in queue:\n",
    "                        continue\n",
    "                    queue.append(next_idx)\n",
    "\n",
    "\n",
    "        s_list = [i for i in s]\n",
    "        visited = [False] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            if not visited[i]:\n",
    "                connected_idxs = []\n",
    "                connected_vals = []\n",
    "                bfs(i)\n",
    "                connected_idxs.sort()\n",
    "                connected_vals.sort()\n",
    "                for idx, val in zip(connected_idxs, connected_vals):\n",
    "                    s_list[idx] = val\n",
    "        return ''.join(s_list)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 找到所有连接的节点\n",
    "    def dfs(self, res, graph, visited, i):\n",
    "        for neighbor in graph[i]:\n",
    "            if not visited[neighbor]:\n",
    "                visited[neighbor] = True\n",
    "                res.append(neighbor)\n",
    "                self.dfs(res, graph, visited, neighbor)\n",
    "\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(len(s))]\n",
    "        visited = [False] * len(s)\n",
    "        for x, y in pairs:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        res = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if not visited[i]:\n",
    "                connected = []\n",
    "                self.dfs(connected, graph, visited, i)\n",
    "                indices = sorted(connected)\n",
    "                string = sorted(res[node] for node in connected)\n",
    "                print(indices, string)\n",
    "                for index,char in zip(indices,string):\n",
    "                    res[index] = char\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        n=len(s)\n",
    "        d=defaultdict(set)\n",
    "        for pair in pairs:\n",
    "            d[pair[0]].add(pair[1])\n",
    "            d[pair[1]].add(pair[0])\n",
    "        visited=set()\n",
    "        \n",
    "        pos=[]\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            visited.add(i)\n",
    "            tem=[i]\n",
    "            stack=deque()\n",
    "            stack.append(i)\n",
    "            while stack:\n",
    "                temp=stack.popleft()\n",
    "                for nex in list(d[temp]):\n",
    "                    if temp==nex:\n",
    "                        continue\n",
    "                    stack.append(nex)\n",
    "                    if nex not in visited:\n",
    "                        tem.append(nex)\n",
    "                        visited.add(nex)\n",
    "                    # print(d[temp],d[nex],temp,nex)\n",
    "                    d[temp].remove(nex) \n",
    "                    d[nex].remove(temp)\n",
    "            pos.append(tem)\n",
    "        char_index=[]\n",
    "        res_list=['a']*n\n",
    "        for i in pos:\n",
    "            temp=[]\n",
    "            for j in i:\n",
    "                temp.append(s[j])\n",
    "            temp.sort()\n",
    "            i.sort()\n",
    "            # print(temp)\n",
    "            # print(i)\n",
    "            for j in range(len(i)):\n",
    "                res_list[i[j]]=temp[j]\n",
    "\n",
    "        return ''.join(res_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        def union(x, y):\n",
    "            xx = find(x)\n",
    "            yy = find(y)\n",
    "            if xx != yy:\n",
    "                if rank[xx] > rank[yy]:\n",
    "                    xx, yy = yy, xx\n",
    "                parent[xx] = yy\n",
    "                areas[yy] += areas[xx]\n",
    "                if rank[yy] == rank[xx]:\n",
    "                    rank[yy] += 1\n",
    "        \n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        m = len(s)\n",
    "        parent = {i: i for i in range(m)}\n",
    "        areas = {i: [i] for i in range(m)}\n",
    "        rank = {i: 1 for i in range(m)}\n",
    "        \n",
    "        for a, b in pairs:\n",
    "            union(a, b)\n",
    "        \n",
    "        tmp = list(s)\n",
    "        pa = set()\n",
    "        \n",
    "        for i in range(m):\n",
    "            pa.add(find(i))\n",
    "        \n",
    "        for j in pa:\n",
    "            tt = [0] * len(areas[j])\n",
    "            for i in range(len(areas[j])):\n",
    "                tt[i] = s[areas[j][i]]\n",
    "            tt.sort()\n",
    "            areas[j].sort()\n",
    "            for index, value in zip(areas[j], tt):\n",
    "                tmp[index] = value\n",
    "        return \"\".join(tmp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from collections import deque\n",
    "class myUF:\n",
    "    def __init__(self, n):\n",
    "        self.m1 = {}\n",
    "        for i in range(n):\n",
    "            self.m1[i] = i\n",
    "\n",
    "    def findP(self, x):\n",
    "        if self.m1[x] == x:\n",
    "            return x\n",
    "        res = self.m1[x]\n",
    "        res2  =self.findP(res)\n",
    "        self.m1[x] = res2\n",
    "        return res2\n",
    "\n",
    "    def uf(self,a,b):\n",
    "        pa = self.findP(a)\n",
    "        pb = self.findP(b)\n",
    "        if pa == pb:\n",
    "            return\n",
    "        self.m1[pa] = pb\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def findPQuick(self, x):\n",
    "        if self.m1[x] == x:\n",
    "            return x\n",
    "        res = self.m1[x]\n",
    "        return self.findPQuick(res)\n",
    "\n",
    "\n",
    "    def getGrp(self):\n",
    "        ret = {}\n",
    "        for i in self.m1:\n",
    "            res1 = self.findPQuick(i)\n",
    "            if res1 not in ret:\n",
    "                ret[res1] = [i]\n",
    "            else:\n",
    "                ret[res1].append(i)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        \"\"\"\n",
    "        s = \"dcab\", pairs = [[0,3],[1,2]]\n",
    "        :param s:\n",
    "        :param pairs:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        pass\n",
    "        a1 = myUF(len(s))\n",
    "        s1 = set()\n",
    "        for i in pairs:\n",
    "            a1.uf(i[0], i[1])\n",
    "            s1.add(i[0])\n",
    "            s1.add(i[1])\n",
    "        ret = ''\n",
    "        grplist = a1.getGrp()\n",
    "        m3 = {}\n",
    "        for i in grplist:\n",
    "            l2 = grplist[i]\n",
    "            vv = [s[i] for i in l2]\n",
    "            vv.sort()\n",
    "            vv2 = deque(vv)\n",
    "            m3[i] = vv2\n",
    "\n",
    "        for (k,v) in enumerate(s):\n",
    "            if k not in s1:\n",
    "                ret += v\n",
    "            else:\n",
    "                pName = a1.findPQuick(k)\n",
    "                first = m3[pName]\n",
    "                toadd = first.popleft()\n",
    "                ret += toadd\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.smallestStringWithSwaps(s = \"dcab\", pairs = [[0,3],[1,2],[0,2]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        ans = list(s)\n",
    "        d = {}\n",
    "        for a, b in pairs:\n",
    "            d[a] = d.get(a, set())\n",
    "            d[b] = d.get(b, set())\n",
    "            d[a].add(b)\n",
    "            d[b].add(a)\n",
    "        \n",
    "        total = set(i for i in d.keys())\n",
    "\n",
    "        while total:\n",
    "            start = set([total.pop()])\n",
    "            run = set()\n",
    "            while start:\n",
    "                new = set()\n",
    "                for i in start:\n",
    "                    new |= d[i]\n",
    "                run |= start\n",
    "                new -= run\n",
    "                start = new\n",
    "            total -= run\n",
    "            t = [ans[i] for i in run]\n",
    "            t.sort(reverse=True)\n",
    "            for i in sorted(list(run)):\n",
    "                ans[i] = t.pop()\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, p):\n",
    "        if p == self.parent[p]:\n",
    "            return p\n",
    "        self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "\n",
    "    def union(self, p, q):\n",
    "        rp = self.find(p)\n",
    "        rq = self.find(q)\n",
    "        if rp != rq:\n",
    "            self.parent[rp] = rq\n",
    "            self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps0(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        for i,j in pairs:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "\n",
    "        vis = set()\n",
    "        ans = list(s)\n",
    "        def dfs(i):\n",
    "            vis.add(i)\n",
    "            res = [i]\n",
    "            for j in g[i]:\n",
    "                if j not in vis:\n",
    "                    res.extend(dfs(j))\n",
    "            return res\n",
    "\n",
    "        for i,x in enumerate(s):\n",
    "            if not i in g or i in vis:\n",
    "                continue\n",
    "            res = dfs(i)\n",
    "            cs = [s[x] for x in res]\n",
    "            res.sort()\n",
    "            cs.sort()\n",
    "            for i, c in zip(res,cs):\n",
    "                ans[i] = c\n",
    "        return \"\".join(ans)\n",
    "\n",
    "    def dfs(self,res,graph,visited,x):\n",
    "        for neighbor in graph[x]:\n",
    "            if not visited[neighbor]:\n",
    "                visited[neighbor] = 1\n",
    "                res.append(neighbor)\n",
    "                self.dfs(res,graph,visited,neighbor)\n",
    "    \n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(len(s))]\n",
    "        visited = [0] * len(s)\n",
    "        for x,y in pairs:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        res = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if not visited[i]:\n",
    "                # 获取连通节点\n",
    "                connected_nodes = []\n",
    "                self.dfs(connected_nodes,graph,visited,i)\n",
    "                # 重新赋值\n",
    "                indices = sorted(connected_nodes)\n",
    "                string = sorted(res[node] for node in connected_nodes)\n",
    "                for j,ch in zip(indices,string):\n",
    "                    res[j] = ch\n",
    "            \n",
    "        return \"\".join(res)\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, p):\n",
    "        if p == self.parent[p]:\n",
    "            return p\n",
    "        self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "\n",
    "    def union(self, p, q):\n",
    "        rp = self.find(p)\n",
    "        rq = self.find(q)\n",
    "        if rp != rq:\n",
    "            self.parent[rp] = rq\n",
    "            self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def smallestStringWithSwaps0(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        for i,j in pairs:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "\n",
    "        vis = set()\n",
    "        ans = list(s)\n",
    "        def dfs(i):\n",
    "            vis.add(i)\n",
    "            res = [i]\n",
    "            for j in g[i]:\n",
    "                if j not in vis:\n",
    "                    res.extend(dfs(j))\n",
    "            return res\n",
    "\n",
    "        for i,x in enumerate(s):\n",
    "            if not i in g or i in vis:\n",
    "                continue\n",
    "            res = dfs(i)\n",
    "            cs = [s[x] for x in res]\n",
    "            res.sort()\n",
    "            cs.sort()\n",
    "            for i, c in zip(res,cs):\n",
    "                ans[i] = c\n",
    "        return \"\".join(ans)\n",
    "\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        for i,j in pairs:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "\n",
    "        vis = [0] * len(s)\n",
    "        ans = list(s)\n",
    "        def dfs(i):\n",
    "            vis[i] = 1\n",
    "            res.append(i)\n",
    "            for j in g[i]:\n",
    "                if not vis[j]:\n",
    "                    dfs(j)\n",
    "\n",
    "\n",
    "        for i,x in enumerate(s):\n",
    "            if not i in g or vis[i]:\n",
    "                continue\n",
    "            res = []\n",
    "            dfs(i)\n",
    "            cs = [s[x] for x in res]\n",
    "            res.sort()\n",
    "            cs.sort()\n",
    "            for i, c in zip(res,cs):\n",
    "                ans[i] = c\n",
    "        return \"\".join(ans)\n",
    "\n",
    "\n",
    "    def dfs(self,res,graph,visited,x):\n",
    "        for neighbor in graph[x]:\n",
    "            if not visited[neighbor]:\n",
    "                visited[neighbor] = 1\n",
    "                res.append(neighbor)\n",
    "                self.dfs(res,graph,visited,neighbor)\n",
    "    \n",
    "    def smallestStringWithSwaps_other(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(len(s))]\n",
    "        visited = [0] * len(s)\n",
    "        for x,y in pairs:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        res = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if not visited[i]:\n",
    "                # 获取连通节点\n",
    "                connected_nodes = []\n",
    "                self.dfs(connected_nodes,graph,visited,i)\n",
    "                # 重新赋值\n",
    "                indices = sorted(connected_nodes)\n",
    "                string = sorted(res[node] for node in connected_nodes)\n",
    "                for j,ch in zip(indices,string):\n",
    "                    res[j] = ch\n",
    "            \n",
    "        return \"\".join(res)\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
